<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>3. 把待搜索区间分成两个部分（重点、最重要的部分在这里） | 算法不好玩</title>
    <meta name="generator" content="VuePress 1.8.2">
    <link rel="icon" href="/book/logo.png">
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.7.1/katex.min.css">
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/github-markdown-css/2.10.0/github-markdown.min.css">
    <meta name="description" content="">
    
    <link rel="preload" href="/book/assets/css/0.styles.e159a327.css" as="style"><link rel="preload" href="/book/assets/js/app.a4355b0d.js" as="script"><link rel="preload" href="/book/assets/js/2.ba785ee6.js" as="script"><link rel="preload" href="/book/assets/js/18.398213f8.js" as="script"><link rel="prefetch" href="/book/assets/js/10.b6950be1.js"><link rel="prefetch" href="/book/assets/js/11.f4ee7d6e.js"><link rel="prefetch" href="/book/assets/js/12.50fe1ace.js"><link rel="prefetch" href="/book/assets/js/13.42356fcc.js"><link rel="prefetch" href="/book/assets/js/14.e740c742.js"><link rel="prefetch" href="/book/assets/js/15.05c628f7.js"><link rel="prefetch" href="/book/assets/js/16.bd9bc9d5.js"><link rel="prefetch" href="/book/assets/js/17.e120b4fc.js"><link rel="prefetch" href="/book/assets/js/19.e29ad0b2.js"><link rel="prefetch" href="/book/assets/js/20.14e30c1c.js"><link rel="prefetch" href="/book/assets/js/21.4f05f6c9.js"><link rel="prefetch" href="/book/assets/js/22.98fbf199.js"><link rel="prefetch" href="/book/assets/js/23.285387f4.js"><link rel="prefetch" href="/book/assets/js/24.852addbe.js"><link rel="prefetch" href="/book/assets/js/25.d30ade13.js"><link rel="prefetch" href="/book/assets/js/26.23dfa040.js"><link rel="prefetch" href="/book/assets/js/27.b6eae7df.js"><link rel="prefetch" href="/book/assets/js/28.97878b08.js"><link rel="prefetch" href="/book/assets/js/29.7217a3d0.js"><link rel="prefetch" href="/book/assets/js/3.f0c15194.js"><link rel="prefetch" href="/book/assets/js/30.0ced5a5a.js"><link rel="prefetch" href="/book/assets/js/31.8f432033.js"><link rel="prefetch" href="/book/assets/js/32.aac9aa62.js"><link rel="prefetch" href="/book/assets/js/33.db835477.js"><link rel="prefetch" href="/book/assets/js/34.a1a59c2a.js"><link rel="prefetch" href="/book/assets/js/35.ed2ef96b.js"><link rel="prefetch" href="/book/assets/js/36.48099c55.js"><link rel="prefetch" href="/book/assets/js/37.32827612.js"><link rel="prefetch" href="/book/assets/js/38.58abec0e.js"><link rel="prefetch" href="/book/assets/js/39.f6eb3874.js"><link rel="prefetch" href="/book/assets/js/4.13ea3b32.js"><link rel="prefetch" href="/book/assets/js/40.80523ed8.js"><link rel="prefetch" href="/book/assets/js/41.f7b72b7a.js"><link rel="prefetch" href="/book/assets/js/42.44e40de9.js"><link rel="prefetch" href="/book/assets/js/43.065f077f.js"><link rel="prefetch" href="/book/assets/js/44.386d9aea.js"><link rel="prefetch" href="/book/assets/js/45.d8a88f16.js"><link rel="prefetch" href="/book/assets/js/46.33bc2083.js"><link rel="prefetch" href="/book/assets/js/47.e7767237.js"><link rel="prefetch" href="/book/assets/js/48.9bb76138.js"><link rel="prefetch" href="/book/assets/js/49.c2ca5c29.js"><link rel="prefetch" href="/book/assets/js/5.32eda204.js"><link rel="prefetch" href="/book/assets/js/50.1242fe24.js"><link rel="prefetch" href="/book/assets/js/51.e8f8117d.js"><link rel="prefetch" href="/book/assets/js/52.eae5648f.js"><link rel="prefetch" href="/book/assets/js/53.39876d83.js"><link rel="prefetch" href="/book/assets/js/6.1c662163.js"><link rel="prefetch" href="/book/assets/js/7.29470445.js"><link rel="prefetch" href="/book/assets/js/8.814b737f.js"><link rel="prefetch" href="/book/assets/js/9.d4211262.js">
    <link rel="stylesheet" href="/book/assets/css/0.styles.e159a327.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/book/" class="home-link router-link-active"><!----> <span class="site-name">算法不好玩</span></a> <div class="links"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="/book/" class="nav-link">
  主页
</a></div><div class="nav-item"><a href="/book/guide/" class="nav-link">
  关于我
</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="基础算法与数据结构" class="dropdown-title"><span class="title">基础算法与数据结构</span> <span class="arrow down"></span></button> <button type="button" aria-label="基础算法与数据结构" class="mobile-dropdown-title"><span class="title">基础算法与数据结构</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>
          排序算法
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/book/algs/01-binary-search/" class="nav-link router-link-active">
  第 1 章 二分查找
</a></li><li class="dropdown-subitem"><a href="/book/algs/recursion/" class="nav-link">
  第 2 章 递归
</a></li></ul></li><li class="dropdown-item"><h4>
          数组里的算法
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/book/algs/01-binary-search/" class="nav-link router-link-active">
  第 4 章 滑动窗口
</a></li><li class="dropdown-subitem"><a href="/book/algs/02-basic-sorting/" class="nav-link">
  第 5 章 双指针
</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="威威道来" class="dropdown-title"><span class="title">威威道来</span> <span class="arrow down"></span></button> <button type="button" aria-label="威威道来" class="mobile-dropdown-title"><span class="title">威威道来</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/book/talk-show/2021-04/" class="nav-link">
  2021 年 4 月
</a></li></ul></div></div><div class="nav-item"><a href="https://leetcode-cn.com/" target="_blank" rel="noopener noreferrer" class="nav-link external">
  力扣
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><a href="https://gitee.com/liweiwei1419/book/pages" target="_blank" rel="noopener noreferrer" class="nav-link external">
  Gitee 部署页面
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"><div class="nav-item"><a href="/book/" class="nav-link">
  主页
</a></div><div class="nav-item"><a href="/book/guide/" class="nav-link">
  关于我
</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="基础算法与数据结构" class="dropdown-title"><span class="title">基础算法与数据结构</span> <span class="arrow down"></span></button> <button type="button" aria-label="基础算法与数据结构" class="mobile-dropdown-title"><span class="title">基础算法与数据结构</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>
          排序算法
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/book/algs/01-binary-search/" class="nav-link router-link-active">
  第 1 章 二分查找
</a></li><li class="dropdown-subitem"><a href="/book/algs/recursion/" class="nav-link">
  第 2 章 递归
</a></li></ul></li><li class="dropdown-item"><h4>
          数组里的算法
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/book/algs/01-binary-search/" class="nav-link router-link-active">
  第 4 章 滑动窗口
</a></li><li class="dropdown-subitem"><a href="/book/algs/02-basic-sorting/" class="nav-link">
  第 5 章 双指针
</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="威威道来" class="dropdown-title"><span class="title">威威道来</span> <span class="arrow down"></span></button> <button type="button" aria-label="威威道来" class="mobile-dropdown-title"><span class="title">威威道来</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/book/talk-show/2021-04/" class="nav-link">
  2021 年 4 月
</a></li></ul></div></div><div class="nav-item"><a href="https://leetcode-cn.com/" target="_blank" rel="noopener noreferrer" class="nav-link external">
  力扣
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><a href="https://gitee.com/liweiwei1419/book/pages" target="_blank" rel="noopener noreferrer" class="nav-link external">
  Gitee 部署页面
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div> <!----></nav>  <ul class="sidebar-links"><li><section class="sidebar-group depth-0"><p class="sidebar-heading open"><span>第 1 章 二分查找</span> <!----></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/book/algs/01-binary-search/" aria-current="page" class="sidebar-link">0. 前言</a></li><li><a href="/book/algs/01-binary-search/1-1-binary-search.html" class="sidebar-link">1. 二分查找的基本问题</a></li><li><a href="/book/algs/01-binary-search/2-expansion.html" class="sidebar-link">2. 二分查找的问题变种</a></li><li><a href="/book/algs/01-binary-search/3-divide-the-search-area-into-two-parts.html" aria-current="page" class="active sidebar-link">3. 把待搜索区间分成两个部分（重点、最重要的部分在这里）</a></li><li><a href="/book/algs/01-binary-search/4-example-explanation.html" class="sidebar-link">4. 例题讲解：「力扣」第 35 题：搜索插入位置</a></li><li><a href="/book/algs/01-binary-search/5-comparison-of-two-writing-methods.html" class="sidebar-link">5. 两种写法对比</a></li><li><a href="/book/algs/01-binary-search/6-some-details.html" class="sidebar-link">6. 一些细节（以问答形式呈现）</a></li><li><a href="/book/algs/01-binary-search/7-practice.html" class="sidebar-link">7. 练习</a></li></ul></section></li><li><section class="sidebar-group depth-0"><p class="sidebar-heading"><span>二分查找习题集</span> <!----></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/book/algs/01-binary-search/0633-sum-of-square-numbers.html" class="sidebar-link">「力扣」第 633 题：平方数之和（中等）</a></li><li><a href="/book/algs/01-binary-search/0069-sqrtx.html" class="sidebar-link">「力扣」第 69 题：x 的平方根（简单）</a></li><li><a href="/book/algs/01-binary-search/0875-koko-eating-bananas.html" class="sidebar-link">「力扣」第 875 题：爱吃香蕉的珂珂（中等）</a></li><li><a href="/book/algs/01-binary-search/1011-capacity-to-ship-packages-within-d-days.html" class="sidebar-link">「力扣」第 1011 题：在 D 天内送达包裹的能力（中等）</a></li><li><a href="/book/algs/01-binary-search/1552-magnetic-force-between-two-balls.html" class="sidebar-link">「力扣」第 1552 题：两球之间的磁力（中等）</a></li></ul></section></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="_3-把待搜索区间分成两个部分-重点、最重要的部分在这里"><a href="#_3-把待搜索区间分成两个部分-重点、最重要的部分在这里" class="header-anchor">#</a> 3. 把待搜索区间分成两个部分（重点、最重要的部分在这里）</h1> <p>根据看到的中间位置的元素的值 <code>nums[mid]</code> 可以把待搜索区间分为两个部分：</p> <ul><li><strong>一定不存在</strong> 目标元素的区间：下一轮搜索的时候，不用考虑它；</li> <li><strong>可能存在</strong> 目标元素的区间：下一轮搜索的时候，需要考虑它。</li></ul> <p>由于 <code>mid</code> 只可能被分到这两个区间的其中一个，即：<code>while</code> 里面的 <code>if</code> 和 <code>else</code> 就两种写法：</p> <ul><li>如果 <code>mid</code> 分到左边区间，即区间分成 <code>[left..mid]</code> 与 <code>[mid + 1..right]</code>，此时分别设置 <code>right = mid</code> 与 <code>left = mid + 1</code>；</li> <li>如果 <code>mid</code> 分到右边区间，即区间分成 <code>[left..mid - 1]</code> 与 <code>[mid..right]</code>，此时分别设置 <code>right = mid - 1</code> 与 <code>left = mid</code>。</li></ul> <p>并且把 <strong>循环可以继续的条件</strong> 写成 <code>while (left &lt; right)</code>。<strong>在上面把待搜索区间分成两个部分的情况下，退出循环以后一定会有 <code>left == right</code> 成立</strong>，因此在退出循环以后，不需要考虑到底返回 <code>left</code> 还是返回 <code>right</code>。</p> <p>这里介绍一个 「<strong>重要的经验</strong>」：</p> <blockquote><p>在 <strong>写 <code>if</code> 语句的时候，通常把容易想到的，不容易出错的逻辑写在 <code>if</code> 的里面</strong>，这样就把复杂的、容易出错的情况放在了 <code>else</code> 的部分，这样编写代码不容易出错。</p></blockquote> <p>什么情况是容易想到的，不容易出错的呢？我的经验是：题目要我们找符合条件 a 的元素，我们就对条件 a 取反面，这样分析不容易出错。</p> <p>例如本题（「力扣」第 35 题），题目要我们找出第一个大于等于 <code>target</code> 的元素的下标，那么小于 <code>target</code> 的元素就一定不是我们要找的。因此 <code>if</code> 语句就是</p> <div class="language-java line-numbers-mode"><pre class="language-java"><code><span class="token keyword">if</span> <span class="token punctuation">(</span>nums<span class="token punctuation">[</span>mid<span class="token punctuation">]</span> <span class="token operator">&lt;</span> target<span class="token punctuation">)</span> <span class="token punctuation">{</span>
	<span class="token comment">// 下一轮搜索区间是 [mid + 1..right]</span>
	left <span class="token operator">=</span> mid <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br></div></div><p>剩下的情况放在 <code>else</code> 中，我们 <strong>甚至可以不用分析 <code>else</code> 是什么情况</strong>。<code>if</code> 的区间是 <code>[mid + 1..right]</code>，它的反面区间就是 <code>[left..mid]</code>，此时 <code>else</code> 就应该设置 <code>right = mid</code>。</p> <p>因此完整的逻辑就是：</p> <div class="language-java line-numbers-mode"><pre class="language-java"><code><span class="token keyword">if</span> <span class="token punctuation">(</span>nums<span class="token punctuation">[</span>mid<span class="token punctuation">]</span> <span class="token operator">&lt;</span> target<span class="token punctuation">)</span> <span class="token punctuation">{</span>
	<span class="token comment">// 下一轮搜索区间是 [mid + 1..right]</span>
	left <span class="token operator">=</span> mid <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
	right <span class="token operator">=</span> mid<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br></div></div><p>上面的叙述，总结起来就一句话：我们 <strong>总是在区间 <code>[left..right]</code> 里查找元素目标</strong>。</p> <p><strong>注意</strong>：我们说的是 <strong>左闭右闭区间</strong>。为什么不是「左闭右开」呢？「左闭右开」当然可以，但是我们 <strong>不想把精力花在思考「右边界是不是可以取到」这件事情上</strong>，这是因为 <strong>任意一个「左闭右开 <code>[left..right)</code> 」区间一定唯一对应一个「左闭右闭 <code>[left..right - 1]</code>」区间</strong>，所以到底是开区间还是闭区间，前后保持一致就可以。</p> <p>根据 <code>mid</code> 位置是不是目标元素，进而判断 <code>mid</code> 的左边是否存在目标元素，<code>mid</code> 的右边是否存在目标元素，只把搜索区间分为两个部分，然后设置 <code>left</code> 和 <code>right</code>，<strong>在设置 <code>left</code> 和 <code>right</code> 的时候，左闭右闭区间的形式是最直观的，这是因为如果是开区间，还需要在脑子里反应一下，右端点不包括</strong>。如果我们觉得二分问题复杂，复杂问题应该简单做。</p> <p>我们再说说把区间分成两个部分的好处：</p> <p>在代码层面，只可能有以下两种情况：</p> <ul><li><code>while(left &lt; right)</code> 与 <code>left = mid + 1</code> 、 <code>right = mid</code> 的搭配；</li> <li><code>while(left &lt; right)</code> 与 <code>left = mid</code> 、 <code>right = mid - 1</code> 的搭配；</li></ul> <p><strong>只有在这两种把区间分成两个部分的划分下，退出循环以后有 <code>left == right</code> 成立，我们不用去讨论返回 <code>left</code> 还是 <code>right</code>（这句话非常重要，大家可以在做题的过程中慢慢体会）</strong>。</p> <blockquote><p>补充说明：有的朋友觉得把区间分为三个部分更清晰，但是一旦分成三个部分，有 <code>mid + 1</code>、<code>mid - 1</code> 出现，退出循环以后就不一定有 <code>left</code> 和 <code>right</code> 重合。我们完全可以这样做，分类讨论的时候分成三个部分，然后把它们的逻辑合并起来。</p></blockquote> <p>在我们的讲解中 <code>while(left &lt; right)</code> 与「定义的区间是 <code>[left..right)</code> 」没有任何关系，请大家不要做多余的解读，我们不讲循环不变量是 <code>[left..right)</code> 的情况，我们只认为区间是「左闭右闭」区间，理由上面也说了，每一个位置的值是不是可以取到，我们需要非常清楚，而不想看到一个开区间，我们在脑子里需要想一下「右端点不包括」。</p> <p><strong>至于为什么是 <code>left = mid + 1</code> 、 <code>right = mid</code> 搭配使用，而 <code>left = mid</code> 、 <code>right = mid - 1</code> 搭配使用，这一点完全不用记忆</strong>，我们画图说明。</p> <p><img src="https://pic.leetcode-cn.com/1617857363-gTiArD-image.png" alt="image.png">{:style=&quot;width:500px&quot;}</p> <p>因此我们再次和大家强调：永远去思考下一轮搜索应该在哪个区间里，就能考虑清楚到底下一轮更新的是 <code>left</code> 还是 <code>right</code> ，到底加不加 <code>1</code>，到底减不减 <code>1</code>。</p></div> <footer class="page-edit"><!----> <!----></footer> <div class="page-nav"><p class="inner"><span class="prev">
      ←
      <a href="/book/algs/01-binary-search/2-expansion.html" class="prev">
        2. 二分查找的问题变种
      </a></span> <span class="next"><a href="/book/algs/01-binary-search/4-example-explanation.html">
        4. 例题讲解：「力扣」第 35 题：搜索插入位置
      </a>
      →
    </span></p></div> </main></div><div class="global-ui"><!----></div></div>
    <script src="/book/assets/js/app.a4355b0d.js" defer></script><script src="/book/assets/js/2.ba785ee6.js" defer></script><script src="/book/assets/js/18.398213f8.js" defer></script>
  </body>
</html>
